package com.llb666.java.leetcode;

/**
 * 给定一副牌，每张牌上都写着一个整数。
 *
 * 此时，你需要选定一个数字 X，使我们可以将整副牌按下述规则分成 1 组或更多组：
 *
 * 每组都有 X 张牌。
 * 组内所有的牌上都写着相同的整数。
 * 仅当你可选的 X >= 2 时返回 true。
 *
 * @author 斌~
 * @version 1.0
 * @date 2021/3/12 12:52 上午
 */
public class LeetCode914 {
    /**
     * 最大公约数算法
     * @param x 数值x
     * @param y 数值y
     * @return 数值x和数值y的最大公约数
     */
    private static int gcd(int x, int y) {
        return y > 0 ? gcd(y, x % y) : x;
    }


    public static boolean hasGroupsSizeX(int[] deck) {
        //统计每个数字的出现次数，数组下标作为计数的数值，对应的值为出现的个数，如：num[1]=2,意思是1这个数字出现了2次
        int[] num = new int[10000];
        for (int x : deck) {
            ++num[x];
        }
        // 分组后每组的个数，初始化为0
        int g = 0;
        //遍历数组，计算各个数字出现的次数的"最大公约数"。计算最大公约数为1 不能分组
        for (int i = 0; g != 1 && i < num.length; ++i) {
            //计算最大公约数，即每组分的数字个数
            g = gcd(g, num[i]);
        }
        //打印最大公约数
        System.out.println(g);
        return g > 1;
    }

    public static void main(String[] args) {
        int[] deck  = {1,2,3,4,4,3,2,1};
        //分组情况 【1，1】【2，2】【3，3】【4，4】
        System.out.println(hasGroupsSizeX(deck));
    }
}
